1. Field of the Invention
The present invention relates to a method, apparatus, and medium for building a grid map in a mobile robot and a method, apparatus, and medium for cell decomposition using the grid map building method, apparatus, and medium, and more particularly, to a method, apparatus, and medium by which a grid map of a wide area is built while a robot is traveling, and a method, apparatus, and medium by which the built grid map is decomposed into one or more cells.
2. Description of the Related Art
Generally, robots have been developed as a method in relation to automation of processes in factories or industrial sites. With the development of automatic control technologies and remote control technologies, robots are generally used to work in extreme environments, such as extremely high or low temperatures, to work in dangerous environments, such as in space or undersea environments, or to perform simple and repetitive work.
Recently, in addition to industrial robots used in industrial sites, robots have been commercialized for use as housework or office work assistants in ordinary families or offices. Leading examples of those robots may include cleaning robots, guide robots and security robots.
In the case of a mobile robot, such as a cleaning robot, in order to specify a route for the robot to travel or an area in which the robot is to operate, first, a map which the robot recognizes is required. Generally, in order to build a map which is recognized by the robot, a map prepared by a user in advance is input, or the robot is made to recognize information on the surroundings or the pose of the robot, by using marks that the robot can recognize, on a floor or ceiling, or the robot itself builds a map of an area in which the robot is to operate, by autonomously traveling in the area.
Though various attempts to develop a method of using a robot to build a map while the robot autonomously travels have been made, most methods employ a plurality of sensors, and therefore have uncertainty and errors caused by errors of the sensors. Also, since the area that the robot recognizes with sensors is usually a limited part of an area for which the robot is building a map, even if a good quality grid map is obtained for this limited part, when the map is completed, the overall structure of the grid map becomes different from the actual map.
FIG. 1 is a schematic diagram illustrating the building of a grid map by a robot according to a conventional technology.
For example, if the original map is about a square room as illustrated in FIG. 1, the robot can build a grid map by going around the inside of the room. However, though each side of the grid map built by the robot may correspond to a straight line, the entire grid map may not be recognized as having a square shape. Accordingly, there has been a problem that due to inaccurate grid maps, the robot cannot perform a desired task at a specified pose.
Also, in relation to a space that is the object of a grid map, a method of decomposing the space into a plurality of cells has been preferred. For example, in the case of a cleaning robot, instead of cleaning a wide space at one time, each room or each part of a living room is decomposed into cells and the robot is made to clean each cell. By doing so, the cleaning robot can be made to clean the entire area uniformly and errors in the position or orientation, which increase as the robot travels, can be reduced. This cell decomposition should be performed considering the direction in which the robot is made to clean the space. Accordingly, there have been problems that cell decomposition cannot be performed simply based on an area or a distance, and the cell decomposition should be performed even for identical areas, so that the robot can clean the space efficiently.
Furthermore, when a grid map is built using an inaccurate sensor, edge irregularities are too big, such that the space cannot be easily decomposed into cells according to a conventional method of cell decomposition using critical points.